package map;

import java.util.*;

class User{
    public int id;
    public int name;
}
public class Test {
    //普通背包问题
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i = 1;i<=n;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int[][] f = new int[n+1][m+1];
        for(int i = 1 ;i<=n;i++){
            for(int j = m;j>=0;j--){
                if(j < v[i]) f[i][j] = f[i-1][j];
                else f[i][j] = Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
        System.out.println(f[n][m]);
    }
    public static void main7(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("liangchen");
        set.add("liangchen");
        set.add("liangchen");
        System.out.println(set);
    }
    public static void main6(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("c",3);
        map.put("b",2);
        map.put("a",1);
        Set<Map.Entry<String,Integer>> set = map.entrySet();
        System.out.println(set);
        for(Map.Entry<String,Integer> entry:set){
            System.out.println(entry.getKey()+" : "+entry.getValue());
        }
    }
    public static void main5(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("c",3);
        map.put("b",2);
        map.put("a",1);
        Collection<Integer> collection = map.values();
        System.out.println(collection);
    }
    public static void main4(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("c",3);
        map.put("b",2);
        map.put("a",1);
//        int a = map.get("a",0);
//        Integer a = map.getOrDefault("a2",0);
//        System.out.println(a);

    }
    public static void main3(String[] args) {
        Map<User,Integer> map = new TreeMap<>();
        map.put(new User(),2);
    }
    public static void main2(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        map.put("c",2);
        map.put("b",2);
        map.put("a",2);
        System.out.println(map);
    }
    public static void main1(String[] args) {
        int[] arr = new int[]{6,3,5,4,9,7,2};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0;i<arr.length;i++){
            binarySearchTree.insert(arr[i]);
        }
        binarySearchTree.inorder(binarySearchTree.root);
    }
}
